public class IntersectionOfTwoLinkedLists {
    // 链表节点定义
    static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { 
            val = x; 
            next = null; 
        }
    }

    // 主方法：查找两个链表的相交节点
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lenA = getLength(headA);
        int lenB = getLength(headB);
        
        // 确定长链表和短链表
        ListNode longer = lenA > lenB ? headA : headB;
        ListNode shorter = lenA > lenB ? headB : headA;
        
        // 长链表先走差值步
        int diff = Math.abs(lenA - lenB);
        while (diff > 0 && longer != null) {
            longer = longer.next;
            diff--;
        }
        
        // 同时遍历，查找相交节点
        while (longer != null && shorter != null) {
            if (longer == shorter) {
                return longer; // 找到相交节点
            }
            longer = longer.next;
            shorter = shorter.next;
        }
        
        return null; // 无相交节点
    }

    // 辅助方法：计算链表长度
    private int getLength(ListNode head) {
        int length = 0;
        ListNode curr = head;
        while (curr != null) {
            length++;
            curr = curr.next;
        }
        return length;
    }

    // 测试用例
    public static void main(String[] args) {
        IntersectionOfTwoLinkedLists solution = new IntersectionOfTwoLinkedLists();
        
        // 构造相交链表：1->2->3->6->7，4->5->6->7（相交于节点6）
        ListNode node6 = new ListNode(6);
        ListNode node7 = new ListNode(7);
        node6.next = node7;
        
        ListNode headA = new ListNode(1);
        headA.next = new ListNode(2);
        headA.next.next = new ListNode(3);
        headA.next.next.next = node6; // 1->2->3->6->7
        
        ListNode headB = new ListNode(4);
        headB.next = new ListNode(5);
        headB.next.next = node6; // 4->5->6->7
        
        ListNode intersection = solution.getIntersectionNode(headA, headB);
        System.out.println("相交节点值为：" + (intersection != null ? intersection.val : "无")); // 输出6
        
        // 构造不相交链表
        ListNode headC = new ListNode(1);
        headC.next = new ListNode(2);
        ListNode headD = new ListNode(3);
        headD.next = new ListNode(4);
        System.out.println("不相交检测结果：" + (solution.getIntersectionNode(headC, headD) != null ? "有" : "无")); // 输出无
    }
}